Автомат. Класифікація автоматів. Поняття про модель цифрового автомата типу Мілі та Мура. Цифровий автомат цей пристрій, що характеризується набором деяких внутрішніх станів A = {a1(t), a2(t), ..., an(t)}= у які воно потрапляє під впливом вхідних сигналів і команд програми рішення задачі. Хай є автомат з одним входом і одним виходом: A = {ai(t)} z(t) (t) Рис.1.3. Цифровий автомат Цифрові автомати можуть бути з "жорсткою", або схемної, логікою і з логікою, що зберігається в пам'яті. Розрізняють два класи автоматів: асинхронні і синхронні. Синхронний автомат характеризується тим, що функціонує під управлінням тактових (або що синхронізують) сигналів - ТС, з постійною тривалістю tТС і постійною частотою fТС, якщо квантування часу рівномірне. Такт (квант) часу ti поєднується з фронтом i-того сигналу ТС. Вхідні сигнали можуть впливати на автомат лише за наявності сигналу ТС і не змінюються протягом tТС. Період проходження сигналів ТС повинен бути більше або рівний часу, який необхідний реальному автомату для переходу з одного стану в інший. Коли розглядається абстрактний автомат, то вважається, що зміна внутрішніх станів автомата відбувається в інтервали часу між суміжними ТС, а вихідні сигнали формуються по фронту чергового ТС.асинхронных В автоматах тривалість інтервалу часу, протягом якого залишається незмінним стан вхідних сигналів, є величиною змінної і визначається часом, який необхідний автомату для установки відповідних вихідних сигналів і завершення переходу в новий стан. Отже, асинхронний автомат повинен формувати яким-небудь відповідним способом сигнал про завершення чергового такту, по якому поточні вхідні сигнали можуть бути зняті, після чого може початися наступний такт, тобто можливо надходження нових вхідних сигналів. Як наголошувалося у розділі 1, абстрактний автомат з одним входом і одним виходом можна представити таким чином: A X Y Для завдання кінцевого автомата фіксуються три кінцеві множини (алфавіту): - безліч можливих вхідних сигналів: X = {x1, x2, ..., xm}; - безліч можливих вихідних сигналів: Y = {y1, y2, ..., yk}; - безліч можливих внутрішніх станів автомата: A = {a0, a1, ..., an}. На цих множинах задають двох логічних операторів: - функцію переходів f, що визначає стан автомата а(t + 1) у момент дискретного часу t + 1 залежно від стану автомата а(t) і значення вхідного сигналу x(t) у момент часу t: а(t + 1)= f[а(t), x(t)]; (10.1) - функцію виходів , що визначає залежність вихідного сигналу автомата у(t) від стану автомата а(t) і вхідного сигналу x(t) у момент часу t: y(t) =  [a(t), x(t)]. (10.2) Крім того, на безлічі станів автомата фіксують один з внутрішніх станів а0 як початковий стан. Поняття стан автомата використовується для опису систем, вихідні сигнали яких залежать не тільки від вхідних сигналів в даний момент часу, але і від деякої передісторії, тобто сигналів, які поступали на входи системи раніше. Отже, цифрові автомати відносяться до последовательностним схем, які, як вже наголошувалося, володіють пам'яттю. Поняття стан автомата відповідає деякій пам'яті про минуле, тому введення цього поняття дозволяє усунути час як явну змінну і виразити вихідні сигнали як функцію станів і вхідних сигналів. Роботу абстрактного автомата слід розглядати стосовно конкретних інтервалів часу, оскільки кожному інтервалу дискретності t відповідатиме свій вихідний сигнал у(t). Отже, функціонування автомата розглядається через дискретні інтервали часу кінцевої тривалості. У абстрактній теорії цифрових автоматів вважається, що вхідні сигнали впливають на синхронний автомат у момент початку кожного i-того інтервалу (кванта) часу, виділеного відповідним синхроімпульсом (тактом), а зміна внутрішніх станів автомата відбувається в інтервали часу між суміжними синхроімпульсами, коли немає дії вхідних сигналів. Оператори, що описують роботу автомата, звичайно задають таблицею переходів і таблицею виходів. У таблиці переходів показують в який стан потрап...